'''
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.


说明：

给定的 n 保证是有效的。

进阶：

你能尝试使用一趟扫描实现吗？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
'''



# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        len=0
        p=head
        while p:
            len+=1
            p=p.next
        # if len==1:
        #     return None
        l=len-n
        p=head
        if l<=0:
            return head.next
        for i in range(0,l-1):
            p=p.next
        p.next=p.next.next
        return head



#递归
class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        global i
        if head is None:  # 找到了最末尾，开始return
            i = 0
            return None
        head.next = self.removeNthFromEnd(head.next, n)
        i += 1
        return head.next if i == n else head #如果正好删除了第一个节点，则从第二个开始返回